#include <stdio.h>
#include <math.h>
int number[210][5];
int select[110];
int array[4][5];
int count;
int selecount;
int larray[2][200];
int lcount[2];



int main()
{
    int i,k,flag,cc = 0,il,i4;
    printf("There are magic squares with invertable primes as follow:\n");
    for(i = 1001;i < 9999;i += 2)
    {
        k = i/1000;
        if(k%2 != 0 && k!=5 && num(i))
        {
            number[count][0] = i;
            process(count++);
            if(number[count-1][2]%2 != 0 &&
               number[count-1][3]%2 != 0 &&
               number[count-1][2]   != 5 &&
               number[count-1][3]   != 5)
            {  
                select[selecount++] = count-1;
            }
        }
    }
    larray[0][lcount[0]++] = number[0][0]/100;
    larray[1][lcount[1]++] = number[0][0]/10;
    for(i = 1;i < count;i++)
    {
        if(larray[0][lcount[0]-1] != number[i][0]/100)
            larray[0][lcount[0]++] = number[i][0]/100;
        if(larray[1][lcount[1]-1] != number[i][0]/10)
            larray[1][lcount[1]++] = number[i][0]/10;
    }
    for(il = 0;il < selecount;il++)
    {
        array[0][0] = select[il];
        copy_num(0);
        for(array[1][0] = 0;array[1][0] < count;array[1][0]++)
        {
            copy_num(1);
            if(!comp_num(2))
                continue;
            for(array[2][0] = 0;array[2][0] < count;array[2][0]++)
            {
                copy_num(2);
                if(!comp_num(3))
                    continue;
                for(i4 = 0;i4 < selecount;i4++)
                {
                    array[3][0] = select[i4];
                    copy_num(3);
                    for(flag = 1,i = 1;flag && i <= 4;i++)
                    {
                        if( !find1(i)) flag=0;
                    }
                    if(flag&&find2())
                    {
                        printf("No.%d\n",++cc);
                        p_array();
                    }
                }
            }
        }
    }
    return 0;
}
num(int number)
{
    int j;
    if(!ok(number)) return(0);
    for(j = 0;number > 0;number /= 10)
      j = j*10+number%10;
      if(!ok(j)) return(0);
      return(1);
}
ok(int number)
{
    int i,j;
    if(number%2 == 0) return(0);
    j = sqrt((double)number)+1;
    for(i = 3;i <= j;i += 2);
    if(number%i == 0) return(0);
    return(1);
}
process(int i)
{
    int j,num;
    num = number[i][0];
    for(j = 4;j >= 1;j--,num /= 10)
    number[i][j] = num%10;
}
copy_num(int i)
{
    int j;
    for(j = 1;j <= 4;j++)
    array[i][j] = number[array[i][0]][j];
}
comp_num(int n)
{
    static int ii;
    static int jj;
    int i,num,k,*p;
    int *pcount;
    switch(n)
    {
        case2:pcount=&lcount[0];
              p=&ii;
              break;
        case3:pcount=&lcount[1];
              p=&jj;
              break;
        default:return(0);
    }
    for(i = 1;i <= 4;i++)
    {
        for(num = 0,k = 0;k < n;k++)
            num = num*10+array[k][i];
        if(num <= larray[n-2][*p])
            for(;*p >= 0&&num < larray[n-2][*p];(*p)--);
        else
            for(;*p < *pcount&&num > larray[n-2][*p];(*p)++);
        if(*p<0||*p>=*pcount)
        {
            *p=0;
            return(0);
        }
        if(num != larray[n-2][*p])
            return(0);
    }
    return(1);
}
find0 (int num)
{
    static int j;
    if(num <= number[j][0])
        for(;j >= 0 && num < number[j][0];j--);
    else for(;j < count && num > number[j][0];j++);
    if(j<0||j>=count)
    {
        j=0;
        return(0);
    }
    if(num == number[j][0]) return(1);
    else return(0);
}
find1(int i)
{
    int num,j;
    for(num = 0,j = 0;j < 4;j++)
        num=num*10+array[j][i];
    return(find0(num));
}
find2(void)
{
    int num1,num2,j,i;
    for(num1 = 0,j = 0;j < 4;j++)
        num1 = num1*10+array[j][j+1];
    for(num2 = 0,j = 0,i = 4;j < 4;j++,i--)
        num2 = num2*10+array[j][i];
    if(find0(num1)) return(find0(num2));
    else return(0);
}

p_array(void)
{
    int i,j;
    for(i = 0;i < 4;i++)
    {
        for(j = 1;j <= 4;j++)
        printf("%6d",array[i][j]);
        printf("\n");
    }
}
//熊贤豪